package com.kobeliu.entity;

import java.util.Stack;

/**
 * 剑指第一天 leetcode 同 155
 *
 *定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * 示例:
 *
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.min();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.min();   --> 返回 -2.
 *
 */

public class Demo_30_No155 {
    /** initialize your data structure here. */
    Stack<Integer> s1;
    Stack<Integer> s2;
    public Demo_30_No155() {
        s1 = new Stack<Integer>(); //实栈
        s2 = new Stack<Integer>(); //辅助栈
    }
    public void push(int x) {
        //每次求出当前这个值对应的最小值，压入辅助栈
        s1.push(x);
        if(s2.isEmpty()){
            s2.push(x);
        }else{
            if(s2.peek() >= x){
                s2.push(x);
            }else{
                s2.push(s2.peek());
            }
        }
    }
    public void pop() {
        if(s1.size()>0){
            s1.pop();
            s2.pop();
        }
    }
    public int top() {
        return s1.peek();
    }
    public int min() {
        return s2.peek();
    }
}
